#include <iostream>

using namespace::std;

void min_heap_fix_up(int *a, int i)
{
    int tmp = a[i];
    int j = (i - 1)/2;
    while (j >= 0 && i != 0) 
    {
        if(tmp >= a[j])
        {
           break; 
        }
        a[i] = a[j];
        i = j;
        j = (i - 1) / 2;
    }
    a[i] = tmp;
}

void min_heap_add(int *a , int n, int num)
{
    a[n - 1] = num;
    min_heap_fix_up(a, n);
}

//找最小的，网上移动
void min_heap_fix_down(int *a, int i, int n)
{
    int tmp = a[i]; 
    int j = 2*i + 1;  //chrildren 
    while(j < n)
    {
        if(j+1 < n && a[j+1] < a[j]) //find smaller one of chrildren
        {
            j++;
        }

        if(tmp < a[j])
        {
            break;
        }
        a[i] = a[j];

        i = j;
        j = 2*i + 1;
    }
    a[i] = tmp;
}

void min_heap_delete(int *a, int n)
{
   int tmp = a[0];
   a[0] = a[n - 1] ;
   a[n - 1] = tmp;
   min_heap_fix_down(a, 0, n - 1);
}

void min_heap_create(int *a, int n)
{
    for(int i = n / 2 - 1; i >= 0; i--)
    {
        min_heap_fix_down(a, i, n);
    }
}

void min_heap_sort(int *a, int n)
{
    for(int i = n - 1; i >= 1; i--)
    {
        int tmp = a[i];
        a[i] = a[0];
        a[0] = tmp;
        min_heap_fix_down(a, 0, i);
    }
}

void print_array(int *a, int n)
{
    for(int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}

int main(int argc, char** argv)
{
    int array[10] = {3, 4, 6, 3, 8, -4, 14, 40, 9, 10};
    int size = sizeof(array)/sizeof(array[0]);

    print_array(array, size); 
    min_heap_create(array, size);
    print_array(array, size); 
    min_heap_sort(array, size);
    print_array(array, size); 

    return 0;
}
